package problem61;

//61.旋转链表
//https://leetcode.cn/problems/rotate-list/?envType=study-plan-v2&envId=top-interview-150

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(k == 0 || head == null) return head;
        //1.求出链表的长度
        int len = 0;
        ListNode cur = head;
        while(cur != null) {
            cur = cur.next;
            len++;
        }
        k = k % len;
        //2.找到链表的第len-k个节点
        ListNode tmp = head;
        int cnt = 0;
        while(cnt < len-k) {
            tmp = tmp.next;
            cnt++;
        }
        //3.拼接len-k后面的节点
        ListNode newHead = new ListNode();
        ListNode tail = newHead;
        while(tmp != null) {
            tail.next = tmp;
            tail = tail.next;
            tmp = tmp.next;
        }
        //4.拼接len-k前面的节点
        cnt = 0;
        cur = head;
        while(cnt < len-k) {
            tail.next = cur;
            cur = cur.next;
            tail = tail.next;
            cnt++;
        }
        tail.next = null;
        return newHead.next;
    }
}